\section{Private-Key Encryption and Pseudorandomness}

\subsection{3.6 Constructing CPA-Secure Encryption Schemes}
\frame{
  \frametitle{3.6.1 Pseudorandom Functions}
  \begin{itemize}
      \item A noção de pseudorandomissidade usada em geradores pseudorandomicos contra eavesdroppers tambem pode ser aplicada para obter segurança contra chosen-plaintext attacks.\\
     \vfill
      \item Para tanto, em vez de usar \textit{strings} pseudorandomicas, usaremos \textit{funções} pseudorandomicas, mais especificamente \textit{keyed functions} \\ 
      \vfill
     \end{itemize}
}

\frame{
  \frametitle{3.6.1 Pseudorandom Functions}
  \begin{itemize}
       \item Uma \textit{keyed function} $F$: \{0,1\}* $\times$ \{0,1\}* $\rightarrow$ \{0,1\}*, onde o 1o parametro é chamado de chave, denotado por $k$ e o 2o paramentro é a entrada, chamada de $input$.\\
         \vfill
        \item Geralmente $k$ é escolhido primeiro e fixado. Assim temos uma funcao $F_{k}$ : \{0,1\}* $\rightarrow$ \{0,1\}*, com entrada, saida e chave tendo o mesmo tamanho.\\
       \vfill 
        \item Essa função é dita eficiente se existir um algoritimo de tempo polinomial que compute $F(k,x)$.\\ 
	\vfill 
        \item Intuitivamente, $F$ é pseudorandomica se $F_{k}$ for indistinguivel a um adversario. Ou seja, ele não puder diferencia-la de uma $f$ escolhida ao acaso do conjunto de todas as funções que mapeam n-bit strings para n-bit strings.\\ 
    \end{itemize}
}
%Conta do f e Fk
\frame{
  \frametitle{3.6.1 Pseudorandom Functions}
Tamanho do conjunto de funções de $F$ e $f$
  \begin{itemize}
       \item $F_{\textit{k}}$ = 2$^{n}$ funções \\
      \vfill 
       \item $f$ = 2$^{n \cdot 2 ^{n}}$ funções \\
       \vfill
       \end{itemize}
}

\frame{
  \frametitle{3.6.1 Pseudorandom Functions}

	\begin{block}{Definition 3.23: Pseudorandom function}
		Let $F$: \{0,1\}* x \{0,1\}* $\rightarrow$ \{0,1\}* efficient, lenght-preserving, keyed function. We say that $F$ is a pseudorandom function if for all PPT distinguishers $D$, there exists a negligible function $negl$ such that:

		\begin{equation}
			\vert\Pr[D^{F_{k}\left( \cdot \right)}(1^{n}) = 1] - \Pr[D^{f(\cdot)}(1^{n}) = 1]\vert \leqq negl(n),
		\end{equation}
		where k $\leftarrow$ \{0,1\}$^{n}$ is chosen uniformly at random and \texttt{f} is chosen uniformly at random from the set of functions mapping n-bit strings to n-bit strings.
	\end{block}
	 Note que o \textit{distinguisher} $D$ não tem acesso a chave $k$. Caso contrario seria trivial distinguir um oráculo para $F_{k}$ de um oráculo para $f$.\\

}

\frame{
    \frametitle{3.6.1 Pseudorandom Functions}
  \begin{itemize}
    	\item É importante perguntar se pseudorandom functions existem e, se sim, sob que pressupostos? \\
	\vfill
	\item Na prática, acredita-se que cifras de bloco agem como funções pseudorandomicas. \\ 
	\vfill
	\item Do ponto de vista teórico, funções pseudorandomicas existem se e somente se geradores pseudorandomicos existem. Portanto, essas funções podem ser construidas baseando-se em qualquer um dos problemas difíceis  usados nos geradores. 	
  \end{itemize}
}



\frame{
    \frametitle{3.6.2 CPA-Secure Encryption Schemes from Pseudorandom Functions}
  \begin{itemize}
    	\item Um primeiro esquema intuitivo seria $Enc_{k}(m) = F_{k}(m)$, entretanto esse método é deterministico e portanto não pode ser CPA-seguro. \\
	\vfill
	\item Para se conseguir uma construção probabilistica, aplica-se a função pseudorandomica a um \textit{valor randomico} $r$. Após, aplica-se o resultado e o texto em claro a um XOR.\\
	\vfill
	\item Essa construção se mantem enquanto a função for aplicada para um input diferente a cada vez. Alem, o $r$ pode se repetir e esse caso precisa ser levado em conta.\\ 	
  \end{itemize}
}

\frame{
    \frametitle{3.6.2 CPA-Secure Encryption Schemes from Pseudorandom Functions}
  
	\begin{block}{Construção 3.24: Secure encryption Scheme for any pseudorandom function}
		Let $F$ be a pseudorandom function. Define a private-key encryption scheme for messages of length $n$ ass follows:
		\begin{itemize}
			\item $Gen$: on input $1^{n}$, choose $k \rightarrow \{0,1\}^{n}$ uniformly at random and output it as the key. \\
			\vfill
			\item $Enc$: on input a key $k \in \{0,1\}^{n}$ and a message $m \in \{0,1\}^{n}$, choose $r\rightarrow \{0,1\}^{n}$ uniformly at random and output the ciphertext\\
			\begin{equation}
				c:= \langle r,F_{k}(r) \oplus m \rangle.
			\end{equation}
			\vfill 
			\item $Dec$: on input a key $k \in \{0,1\}^{n}$ and a ciphertext $c = \langle r,s \rangle$, output the plaintext message
			\begin{equation}
				m:= F_{k}(r) \oplus s.
			\end{equation}\\
		\end{itemize}
	\end{block}
	
}

\frame{
    \frametitle{3.6.2 CPA-Secure Encryption Schemes from Pseudorandom Functions}
  \begin{itemize}
    	\item Intuitivamente, essa construção se mantem segura porque $F_{k}(r)$ aparenta completamente randomica para um advesário que observe uma cifra $\langle r,s \rangle$. \\
	\vfill	
	\item Entretanto, a segurança só se mantem enquanto $r$ não tiver sido usado pelo oráculo para responder uma das consultas do adversário. \\
	\vfill	
	\item Mais ainda, a chance de $r$ se repetir ocorre somente com uma probabilidade negligenciavel.
  \end{itemize}
}

\frame{
    \frametitle{3.6.2 CPA-Secure Encryption Schemes from Pseudorandom Functions}
	\begin{block}{Theorem 3.25}
		If $F$ is a pseudorandom function, then Construction 3.24 is a fixed-legth private-key encryption scheme for messages of lenght $n$ that has indistinmguishable encryptions under a chosen-plaintext attack.
	\end{block}	
}

\frame{
    \frametitle{3.6.2 CPA-Secure Encryption Schemes from Pseudorandom Functions}
	\begin{block}{Prova}
		Para um adversário $\mathcal{A}$ que faz no máximo $q(n)$ consultas, temos:
		\begin{equation}
			Pr[PrivK^{cpa}_{\mathcal{A},\widetilde{\Pi}}(n) = 1] \leqq \frac{1}{2} + \frac{q(n)}{2^{n}}.
		\end{equation}
	\end{block}
	
	
}

\frame{
    \frametitle{3.6.2 CPA-Secure Encryption Schemes from Pseudorandom Functions}
	\begin{block}{Analysis of the Repeat event}
		Let $Repeat$ denote the event that $r_{c}$ is used by the encryption oracle to answer at least one of $\mathcal{A}$'s querys. The probability that $Repeat$ occurs is at most $\frac{q(n)}{2^{n}}$, and the probability that $\mathcal{A}$ succeeds in $PrivK^{cpa}_{\mathcal{A},\widetilde{\Pi}}$ if $Repeat$ does not occur is exactly $\frac{1}{2}$. Thus we have:
		\begin{equation}
			\Pr[PrivK^{cpa}_{\mathcal{A},\widetilde{\Pi}}(n) = 1] \\

			= \Pr[PrivK^{cpa}_{\mathcal{A},\widetilde{\Pi}}(n) = 1 \wedge Repeat] +  \Pr[PrivK^{cpa}_{\mathcal{A},\widetilde{\Pi}}(n) = 1 \wedge \overline{Repeat}] \\

			\leqq \Pr[Repeat] + \Pr[PrivK^{cpa}_{\mathcal{A},\widetilde{\Pi}}(n) = 1 | \overline{Repeat}] 

			\leqq  \frac{q(n)}{2^{n}} + \frac{1}{2}.
		\end{equation}
	\end{block}	
}


\frame{
    \frametitle{3.6.2 CPA-Secure Encryption Schemes from Pseudorandom Functions}
	Fixando para um adversário PPT $\mathcal{A}$ e definindo $\varepsilon$ por
		\begin{equation}
			\varepsilon (n) \doteq \Pr[PrivK^{cpa}_{\mathcal{A},\Pi}(n) = 1]  - \frac{1}{2}.
		\end{equation}
	Chegamos a :
 		\begin{equation}
			\Pr[D^{F_{k}\left( \cdot \right)}(1^{n}) = 1] - \Pr[D^{f(\cdot)}(1^{n}) = 1] \geqq \varepsilon (n) - \frac{q(n)}{2^{n}}
		\end{equation}
	Assumindo $F$ uma função pseudorandomica, segue que $\varepsilon (n) - \frac{q(n)}{2^{n}}$ é negligenciavel. Já que $q$ é polinomial, isso implica que  $\varepsilon$ é negligenciavel, e portanto $\Pi$ é CPA seguro. $\blacksquare$
	
}

\frame{
    \frametitle{3.6.3  Pseudorandom Permutations and Block Cipher}
	  \begin{itemize}
    		\item Seja $F$: \{0,1\}* $\times$ \{0,1\}* $\rightarrow$ \{0,1\}* uma keyed function, $F$ será uma \textit{keyed permutation} se para todo $k$ $F_{k}(\cdot)$ for uma bijeção. \\
		\vfill	
		\item Uma \textit{keyed permutation} será eficiente se existir um algoritmo de tempo polinomial que resolva $F_{k}$ e $F_{k}^{-1}$ .\\
		\vfill	
		\item De maneira análoga e intuitiva uma \textit{keyed permutation}, assim como uma \textit{keyed function},  tambem é uma indistinguivel.
	\end{itemize}
	
}

\frame{
    \frametitle{3.6.3  Pseudorandom Permutations and Block Cipher}
	\begin{block}{Definition 3.28 strong pseudorandom permutation}
		We say that $F$ is a \textit{strong pseudorandom permutation} if for all $PPT$ \textit{distinguisher} $D$, there exists a negligible function $negl$ such that:
		\begin{equation}
			|\Pr[D^{F_{k}( \cdot),F_{k}^{-1}( \cdot),}(1^{n}) = 1] - \Pr[D^{f(\cdot),f^{-1}(\cdot)}(1^{n}) = 1] | \leqq negl(n),
		\end{equation}
	\end{block}
	
}

\frame{
    \frametitle{3.6.3  Pseudorandom Permutations and Block Cipher}
	  \begin{itemize}
    		\item Analogamente a \textit{steam ciphers}, que podem modelar geradores pseudorandomicos, cifras de bloco modelam \textit {strong pseudorandom permutations } . \\
		\vfill	
    		\item Assim como \textit{steam ciphers}, cifras de bloco não são esquemas seguros de encriptação, entretanto eles são usados para construir tais esquemas. \\
		\vfill	
		\item De maneira análoga e intuitiva uma \textit{keyed permutation}, assim como uma \textit{keyed function},  tambem é uma indistinguivel.
	\end{itemize}
	
}

\frame{
    \frametitle{3.6.4 Modes of Operation}
	  \begin{itemize}
    		\item Um modo de operação é essencialmente uma forma de encriptar uma mensagem de tamanho arbitrario. \\
		\vfill	
    		\item Mensagens de tamanho arbitrario podem ser concatenadas de forma não ambigua para serem multiplas do tamanho do bloco desejado\\
		\vfill	
		\item Os quatro modelos apresentados são:
			  \begin{itemize}
    			\item Mode 1 - Electronic Code Book (ECB) mode. \\
			\vfill	
			\item Mode 2 - Cipher Block Chaining (CBC) mode.\\
			\vfill	
			\item Mode 3 - Output Feedback (OFB) mode. \\
			\vfill	
			\item Mode 4 - Counter (CTR) mode.\\
		\end{itemize}
	\end{itemize}
	
}

\frame{
  \frametitle{ Mode 1 - Electronic Code Book (ECB) mode}
  \begin{itemize}
    \item Dada uma mensagem em claro $ m = m_{1},m_{1},. . . , m_{l}$, a cifra é obtida encriptando cada bloco separadamente.\\
      \vfill
    \item Encriptar nesse caso, signifca uma aplicação direta do permutação pseudorandomica no bloco de texto em  claro. Ou seja, $c = \langle F_{k}(m_{1}), F_{k}(m_{2}), . . . ,F_{k}(m_{l}) \rangle;$
      \vfill
    \item Esse esquema é determistico e portanto não é CPA-seguro, nem é indistinguivel na presença de um \textit{eavesdropper}.
      \vfill
    \item ECB não deve ser usado nunca e está incluido somente para referencia historica.
      \vfill
    \item A mensagem embaralhada é chamada de texto cifrado. 
      \vfill
 \end{itemize}
}

\frame{
  \frametitle{ Mode 2 - Cipher Block Chaining (CBC) mode}
  \begin{itemize}
    \item Escolhe-se um vetor inicial $IV$ de tamanho $n$ .\\
      \vfill
    \item Os blocos cifrados são gerados aplicando a permutação pseudorandomica ao XOR do bloco de texto em claro corrente. \\
      \vfill
    \item Ou seja, $c_{0} := IV$ e depois para $i = 1$ ate $l$, $c_{i} := F_{k}(c_{i-1} \oplus m_{i})$
      \vfill
    \item $IV$ é mandado em claro como parte do texto cifrado. Isso é crucial para que a decriptação possa ser feita.
      \vfill
    \item Maior desvantagem: A encriptação tem que ser feita sequencialmente.
      \vfill
 \end{itemize}
}

\frame{
  \frametitle{ Mode 3 - Output Feedback (OFB) mode}
  \begin{itemize}
    \item Essencialmente, esse modo usa a cifra de bloco para gerar um \textit{pseudorandom stream} que então é aplicada messagem com um XOR.\\
      \vfill
    \item Ou seja, $r_{0} := IV$, define-se o bloco $r_{i} := F_{k}(r_{i-1})$\\
      \vfill
    \item Depois, cada bloco do texto em claro é encriptado aplicando XOR ao bloco apropriado do \textit{stream}; $c_{i} := m_{i}i \oplus r_{i}$\\
      \vfill
   \item Assim como no CVC, $IV$ é mandado em claro como parte do texto cifrado. Entretanto não é necessario que $F$ seja inversivel.\\
      \vfill
   \item Esse modo tambem precisa ser feito sequencialmente, mas é possivel calcular o \textit{stream} previamente, por um preprocessador.\\
      \vfill
 \end{itemize}
}

\frame{
  \frametitle{   Mode 4 - Counter (CTR) mode}
  \begin{itemize}
    \item Existem algumas variantes do CTR. O modo descrito aqui é o \textit{randomized counter mode}
      \vfill
    \item Assim como no OFB, o CTR tambem usa  esse modo usa a cifra de bloco para gerar um \textit{pseudorandom stream}\\
      \vfill
    \item 1o um $IV \rightarrow \{0,1\}^{n}$ é escolhido e denotado $ctr$
      \vfill
    \item Depois o \texit{stream} é gerado computando $r_{i} := F_{k}(ctr + i)$. $ctr$ e $i$ são vistos como inteiros e a soma é modulo $2^{n}$ \\
      \vfill
    \item Finalmente cada bloco cifrado é computado por $c_{i} := r_{i} \oplus m_{i}$ e $IV$ é mandado em claro novamente.
      \vfill
    \item Esse modo pode ser feito paralelamente, é possivel gerar \texit{pseudorandom streams} previamente e é possivel decriptar um bloco qualquer independente dos outros blocos.
      \vfill
 \end{itemize}
}

\frame{
  \frametitle{   Mode 4 - Counter (CTR) mode}
	\begin{block}{Theorem 3.29}
		If $F$ is a pseudorandom function, then randomized counter mode (as described above) has indistinguishable encryptions under a chose-plaintext attack.
	\end{block}	
}

\frame{
  \frametitle{   Mode 4 - Counter (CTR) mode}
	\begin{block}{Prova}
		Let $Overlap$ denote the event that $Overlap_{i}$ occurs for some $i$. Since there are at most $q(n)$ oracle queries, a union bound gives
		\begin{equation}
			\Pr[Overlap] \leqq \sum _{i=1}^{q(n)} \Pr[Overlap_{i}].
		\end{equation}
	Since there are $2q(n)-1$ values of $ctr_{i}$ for which $Overlap_{i}$ can occur, and $ctr_{i}$ is chosen uniformly at random form $\{0,1\}^{n}$, we see that
	\begin{equation}
			\Pr[Overlap_{i}] = \frac{2q(n) - 1}{2^{n}}  \longrightarrow \Pr[Overlap] \leqq \frac{2q(n) ^{2}}{2^{n}}
	\end{equation}
	Following
	\begin{equation}
			\Pr[PrivK^{cpa}_{\mathcal{A},\widetilde{\Pi}}(n) = 1] \leqq \frac{2q(n) ^{2}}{2^{n}} + \frac{1}{2}.
		\end{equation}
	\end{block}	
}

\frame{
  \frametitle{   Mode 4 - Counter (CTR) mode}
  \begin{itemize}
            \item Já que q é polynomial, $\frac{2q(n) ^{2}}{2^{n}} $ é negligenciavel.\\
            \vfill
            \item Assim, o esquema \widetilde{\Pi}} é CPA-seguro\\
           \vfill
           \item Intuitivamente, \Pi tambem é um esquema CPA-seguro, já que trocar a função randomica pela pseudorandomica não deve ter nenhum efeito para o adversário.
           \vfill
  \end{itemize}
}

\frame{
  \frametitle{ Block lenght and security}
  \begin{itemize}
            \item $IV$ tem o efeito de randomizar o processo de encriptação e garantir que sempre uma nova cifra de bloco é aplicada a entrada.\\
            \vfill
            \item Esse pressuposto é importante pois caso contrario a segurança é violada.\\
           \vfill
           \item Vale ressaltar que alem da chave, o tamanho da cifra de bloco tambem deve ser levando em conta na hora de avaliar a segurança\\
           \vfill
           \item Nenhum dos modos a cima citados garantem integridade a mensagem.\\
           \vfill
  \end{itemize}
}

\subsection{3.7 Security Against Chosen-Ciphertext Attacks (CCA)}

\frame{
  \frametitle{ Chosen-Ciphertext Attacks (CCA) }
  \begin{itemize}
            \item No CCA, o adversario pode decriptar textos cifrados ( com exceção da cifra em questão)\\

           	\begin{block}{The CCA indistinguishability experiment $PrivK_{\mathcal{A}, \Pi}^{cca}(n)$:}
  	\begin{enumerate}
            	\item A key $k$ is generated by running $Gen(1^{n})$.\\
            	\vfill
           	 \item The adversary $\mathcal{A}$ is given input $1^{n}$ and oracle acess to $Enc_{k}(\cdot)$ and $Dec_{k}(\cdot)$. It outputs a pair of messages $m_{0}$, $m_{1}$ of the same lenght.\\
           	\vfill
           	\item A random bit $\rightarrow \{0,1\}$ is chosen, and then a ciphertext c $\rightarrow$  $Enc_{k}(m_{b})$ is computed and given to $\mathcal{A}$. We call $c$ the challenge ciphertext.\\
           	\vfill
           	\item  The adversary  $\mathcal{A}$ continues to have oracle access to $Enc_{k}(\cdot)$ and $Dec_{k}(\cdot)$, but is not allowed to query the latter on the challenge ciphertext itself. Eventually $\mathcal{A}$  outputs a bit $b'$.\\
        	   \vfill
		\item The output of the experiment is defined to be 1 if $b' = b$, and 0 otherwise.
	  \end{enumerate}
		\end{block}	
  \end{itemize}
}

\frame{
  \frametitle{ Chosen-Ciphertext Attacks (CCA) }
  \begin{itemize}
            \item Apesar de partes honestas supostamente não decriptarem uma cifra para o adversário, é possivel que o adversário influencie no que é decriptado.\\
            \vfill
            \item Nenhum dos esquemas estudados até agora são CCA-seguros.\\

  \end{itemize}
}
